{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Positions on Street With Required Brightness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: meetRequirement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算街道上满足所需亮度的位置数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code>。一条完全笔直的街道用一条从 <code>0</code> 到 <code>n - 1</code> 的数轴表示。给你一个二维整数数组 <code>lights</code>，表示街道上的路灯。每个 <code>lights[i] = [position<sub>i</sub>, range<sub>i</sub>]</code>&nbsp;表示在位置 <code>position<sub>i</sub></code> 有一盏路灯，从 <code>[max(0, position<sub>i</sub> - range<sub>i</sub>), min(n - 1, position<sub>i</sub> + range<sub>i</sub>)]</code>&nbsp;(<strong>包含边界</strong>) 开始照亮该区域。</p>\n",
    "\n",
    "<p>位置 <code>p</code> 的&nbsp;<strong>亮度&nbsp;</strong>定义为点亮位置 <code>p</code> 的路灯的数量。给定一个大小为 <code>n</code> 的整数数组 <code>requirement</code>，数组的&nbsp;<strong>下标从 0 开始</strong>，其中 <code>requirement[i]</code> 是街道上第 <code>i</code> 个位置的最小&nbsp;<strong>亮度</strong>。</p>\n",
    "\n",
    "<p>返回<em>街道上 <code>0</code> 到 <code>n - 1</code> 之间&nbsp;<strong>亮度至少满足</strong>&nbsp;</em><code>requirement[i]</code><em> 的位置 <code>i</code> 的数量。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/11/screenshot-2022-04-11-at-22-24-43-diagramdrawio-diagramsnet.png\" style=\"height: 150px; width: 579px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 5, lights = [[0,1],[2,1],[3,2]], requirement = [0,2,1,4,1]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong>\n",
    "- 第一盏路灯照亮区域范围为 [max(0,0 - 1)， min(n - 1,0 + 1)] =[0,1](含边界)。\n",
    "- 第二盏路灯的点亮范围为 [max(0,2 - 1)， min(n - 1,2 + 1)] =[1,3](含边界)。\n",
    "- 第三盏路灯照亮区域范围为 [max(0,3 - 2)， min(n - 1,3 + 2)] =[1,4](含边界)。\n",
    "\n",
    "- 位置 0 被第一盏路灯覆盖。它被 1 个路灯覆盖，大于 requirement[0]。\n",
    "- 位置 1 被第一、第二和第三个路灯覆盖。被 3 个路灯覆盖，大于 requirement[1]。\n",
    "- 位置 2 由第二和第三路灯覆盖。被 2 个路灯覆盖，大于 requirement[2]。\n",
    "- 位置 3 由第二和第三路灯覆盖。它被 2 个路灯覆盖，比 requirement[3] 少。\n",
    "- 位置 4 被第三个路灯覆盖。它被 1 盏路灯覆盖，等于 requirement[4]。\n",
    "\n",
    "位置 0、1、2、4 满足要求，因此返回4。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1, lights = [[0,1]], requirement = [2]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "- 第一盏路灯照亮区域范围为 [max(0,0 - 1)， min(n - 1,0 + 1)] =[0,0](含边界)。\n",
    "- 位置 0 被第一盏路灯覆盖。它被 1 个路灯覆盖，比 requirement[0] 少。\n",
    "- 返回0，因为没有位置满足亮度要求。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= lights.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= position<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>0 &lt;= range<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>requirement.length == n</code></li>\n",
    "\t<li><code>0 &lt;= requirement[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-positions-on-street-with-required-brightness](https://leetcode.cn/problems/count-positions-on-street-with-required-brightness/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-positions-on-street-with-required-brightness](https://leetcode.cn/problems/count-positions-on-street-with-required-brightness/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1],[2,1],[3,2]]\\n[0,2,1,4,1]', '1\\n[[0,1]]\\n[2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        diff = [0] * (n + 1)\n",
    "        ans = 0\n",
    "        for l in lights:\n",
    "            diff[max(0, l[0] - l[1])] += 1\n",
    "            diff[min(n - 1, l[0] + l[1]) + 1] -= 1\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur += diff[i]\n",
    "            if cur >= requirement[i]:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        cf=[0]*(n+1)\n",
    "        for p,r in lights:\n",
    "            ll=max(0,p-r)\n",
    "            rr=min(n,p+r+1)\n",
    "            cf[ll]+=1\n",
    "            cf[rr]-=1\n",
    "        l=0\n",
    "        res=0\n",
    "        for i,r in enumerate(requirement):\n",
    "            l+=cf[i]\n",
    "            if l>=r:res+=1\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        temp=[0]*(n+1)\n",
    "        m=n\n",
    "        for i,j in lights:\n",
    "            temp[max(i-j,0)]+=1\n",
    "            temp[min(i+j+1,n)]-=1\n",
    "            m=max(m,i+j+1)\n",
    "        ans,res=0,0\n",
    "        n=len(requirement)\n",
    "        for i in range(m):\n",
    "            if i>n:\n",
    "                break\n",
    "            res+=temp[i]\n",
    "            if i<n and res>=requirement[i]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        brightness=[0]*(n+1)\n",
    "        for pos,ran in lights:\n",
    "            a=max(0,pos-ran)\n",
    "            b=min(n-1,pos+ran)\n",
    "            brightness[a]+=1\n",
    "            brightness[b+1]-=1\n",
    "\n",
    "        ans=temp=0\n",
    "        for i in range(n):\n",
    "            temp+=brightness[i]\n",
    "            if temp>=requirement[i]:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        diff = [0] * (n + 1)\n",
    "        for p, r in lights:\n",
    "            diff[max(0, p - r)] += 1\n",
    "            diff[min(n, p + r + 1)] -= 1\n",
    "        ans = cur = 0\n",
    "        for r, d in zip(requirement, diff):\n",
    "            cur += d\n",
    "            ans += int(cur >= r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 差分数组\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        diff = [0] * (n + 1)\n",
    "        for p, r in lights:\n",
    "            diff[max(0, p - r)] += 1\n",
    "            diff[min(n, p + r + 1)] -= 1\n",
    "\n",
    "        ans = cur = 0\n",
    "        for r, d in zip(requirement, diff):\n",
    "            cur += d\n",
    "            ans += int(cur >= r)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        prefix = [0] * (n + 1)\n",
    "        for pos, rng in lights:\n",
    "            prefix[max(0, pos-rng)] += 1\n",
    "            prefix[min(n, pos+rng+1)] -= 1\n",
    "\n",
    "        cnt = 0 if prefix[0] < requirement[0] else 1\n",
    "        for i in range(1, n):\n",
    "            prefix[i] += prefix[i-1]\n",
    "            cnt = cnt if prefix[i] < requirement[i] else cnt + 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        prefix = [0] * (n + 1)\n",
    "        for pos, rng in lights:\n",
    "            prefix[max(0, pos-rng)] += 1\n",
    "            prefix[min(n, pos+rng+1)] -= 1\n",
    "\n",
    "        cnt = 0 if prefix[0] < requirement[0] else 1\n",
    "        for i in range(1, n):\n",
    "            prefix[i] += prefix[i-1]\n",
    "            cnt = cnt if prefix[i] < requirement[i] else cnt + 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        l = [0] * n\n",
    "\n",
    "        def incr(l, i, j, v): # 左闭右闭区间\n",
    "            l[i] += v\n",
    "            if j < n - 1:\n",
    "                l[j + 1] -= v\n",
    "\n",
    "        for p, r in lights:\n",
    "            i = max(0, p - r)\n",
    "            j = min(n - 1, p + r)\n",
    "            incr(l, i, j, 1)\n",
    "\n",
    "        arr = [0] * n\n",
    "        arr[0] = l[0]\n",
    "        for i in range(1, n):\n",
    "            arr[i] = arr[i - 1] + l[i]\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if requirement[i] <= arr[i]:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        diff = [0] * (n + 1)\n",
    "        for x, y in lights:\n",
    "            diff[max(0, x - y)] += 1\n",
    "            diff[min(n, x + y + 1)] -= 1\n",
    "        diff = list(accumulate(diff))\n",
    "        return sum(d >= r for d, r in zip(diff, requirement))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        f = [0] * (n + 1)\n",
    "        for p, r in lights:\n",
    "            s, e = max(0, p - r), min(n - 1, p + r)\n",
    "            f[s] += 1\n",
    "            f[e + 1] -= 1\n",
    "        nums = list(accumulate(f[:-1]))\n",
    "        return sum(n >= r for n, r in zip(nums, requirement))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        temp=[0]*1000000\n",
    "        m=n\n",
    "        for i,j in lights:\n",
    "            temp[max(i-j,0)]+=1\n",
    "            temp[i+j+1]-=1\n",
    "            m=max(m,i+j+1)\n",
    "        ans,res=0,0\n",
    "        n=len(requirement)\n",
    "        for i in range(m):\n",
    "            res+=temp[i]\n",
    "            if i<n and res>=requirement[i]:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:\n",
    "        light_degrees = np.zeros(n)  # 表示每一个坐标的亮度，1就代表被一个灯照到，2就代表被2盏灯照到\n",
    "        for p, r in lights:\n",
    "            l, u = max(0, p-r), min(n-1, p+r)\n",
    "            light_degrees[l:u+1] += 1  # 被照到的坐标亮度+1\n",
    "        \n",
    "        return int(np.sum(light_degrees >= np.array(requirement)))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
